#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6+6;

int cnt[N];
int flag[N],sum[N];


signed main(){
    memset(cnt,0,sizeof(cnt));
    for ( int i=1; i<N; i++ ){
        for ( int j=i; j<N; j+=i ){
            cnt[j]++;
        }
    }

    memset(flag,0,sizeof(flag));
    memset(sum,0,sizeof(sum));

    for ( int i=1; i<N; i++ ){
        if ( cnt[i] <= 4 ) flag[i] = 1;
    }

    for  ( int i=0; i<N; i++ ){
        sum[i] = sum[i-1] + flag[i];
    }

    int t; cin >> t; while(t--){
        int l,r; cin >> l >> r;
        cout << sum[r] - sum[l-1] << '\n';
    }    
    

    
}
